package trees;

public class ConvertTreToArrayInEfficientManner {

	static class Node {
		int val;
		Node left, right;

		public Node(int v) {
			this.val = v;
		}
	}

	public static void preOrderTraversal(Node n) {
		if (n != null) {
			System.out.println(n.val);
			preOrderTraversal(n.left);
			preOrderTraversal(n.right);
		}
	}

	public static int[] toArray(Node root, int size) {
		int[] array = new int[size];

		assignValueToArray(root, array, 0, size);

		return array;
	}

	private static Node restore(int[] array) {

		if (array == null || array.length < 1) {
			return null;
		} else {

			Node root = new Node(array[0]);
			for (int i = 1; i < array.length; i++) {
				insert(root, array[i]);
			}
			return root;

		}
	}

	private static void insert(Node n, int value) {

		Node newNode = new Node(value);
		boolean inserted = false;
		while (!inserted) {
			if (n.val > value) {
				if (n.left == null) {
					n.left = newNode;
					inserted = true;
				} else {
					n = n.left;
				}
			} else {
				if (n.right == null) {
					n.right = newNode;
					inserted = true;
				} else {
					n = n.right;
				}
			}
		}
	}

	private static int assignValueToArray(Node node, int[] array, int i,
			int size) {

		if (node != null) {
			array[i++] = node.val;
			i = assignValueToArray(node.left, array, i, size);
			i = assignValueToArray(node.right, array, i, size);
		}
		return i;
	}

	/**
	 * 
	 */
	public static void main(String[] args) {

		Node n1 = new Node(7);
		Node n2 = new Node(3);
		Node n3 = new Node(6);
		Node n4 = new Node(4);
		Node n5 = new Node(15);
		Node n6 = new Node(10);
		Node n7 = new Node(30);
		Node n8 = new Node(18);

		n1.left = n2;
		n1.right = n5;
		n2.right = n3;
		n3.left = n4;
		n5.left = n6;
		n5.right = n7;
		n7.left = n8;

		preOrderTraversal(n1);

		int[] array = toArray(n1, 8);

		for (int i : array) {
			System.out.print(i + " ");
		}
		System.out.println();
		
		Node newNode = restore(array);
		preOrderTraversal(n1);
	}

}
